package jianzhi;

/**
 * description:
 * author:zt
 * date:2021-09-01
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 */
public class jianzhi56 {
    //位运算解法
    public int[] singleNumbers(int[] nums) {
        int ret = 0;
        for (int n : nums) {
            ret ^= n;
        }
        int div = 1;
        while ((div & ret) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int n : nums) {
            if ((div & n) != 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return new int[]{a, b};
    }

    //排序解法
    // public int[] singleNumbers(int[] nums) {
    //     int[] res = new int[2];
    //     int index = 0;
    //     Arrays.sort(nums);
    //     int i = 0;
    //     while(i < nums.length-1){
    //         if(nums[i]!=nums[i+1]){
    //             res[index++] = nums[i++];
    //             if(index>=2) break;
    //         }else {
    //             i += 2;
    //         }
    //     }
    //     if(index<2) res[index] = nums[nums.length-1];
    //     return res;
    // }

    //哈希表解法
    // public int[] singleNumbers(int[] nums) {
    //     HashMap<Integer,Integer> map = new HashMap<>();
    //     for(int i : nums){
    //         map.put(i,map.getOrDefault(i,0)+1);
    //     }
    //     int[] res = new int[2];
    //     int i = 0;
    //     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    //         if(entry.getValue()!=2) {
    //             res[i] = entry.getKey();
    //             if(++i>=2) break;
    //         }
    //     }
    //     return res;
    // }
}
